其他
看看技术大牛是如何让《我的世界》运行的更快？
先进的洞穴剔除算法(the Advanced Cave Culling Algorithm™)是我在开发0.9版本的MCPE（MineCraftPocket Edtion，也就是《我的世界》移动版）的时候偶然想到的一个算法，那个时候我们正在尝试在世界中生成洞穴，并且因为游戏运行的太慢而饱受打击-在当时的设备上帧率很难达到40fps!
幸运的是，我偶然想出来的这种剔除算法表现的非常好，能够把剔除的几何比率从50%提升到99%（是的，你没看错，就是99%！），因此我们就可以在所有的手机上生成洞穴而不仅仅是在那些最强大的设备上生成洞穴。 最重要的是，当这个算法被移植到个人电脑版以后，它对《我的世界》个人电脑版的运行速度也有一个很大的提升：） 我认为讲述下这个算法具体是如何工作的以及它背后的原理和思想对于很多人来说是有意思的，并且它可能对其他正在开发的体素游戏（voxel game）也是会有帮助的，所以本文将介绍下先进的洞穴剔除算法(theAdvanced Cave Culling Algorithm™)是如何工作的。 是的，洞穴会让游戏变得很慢在《我的世界》中，探索洞穴是件非常有意思的事情，并且由于洞穴里面像海绵一样的结构以及巨大的可行走区域，很容易就在洞穴里面迷路。洞穴一直是我们希望在《我的世界》移动版里面想要表现的游戏性的一部分。
但是，尽管洞穴对于游戏性来说是件很酷的事情，但是他们却是性能消耗的终极噩梦。
这主要是由于以下几方面的原因：
洞穴的渲染需要对它们的表面进行细分（tessellate），这将导致生成极其巨量的三角形并需要对这些三角形进行渲染。
这些洞穴真的是非常混乱和扭曲。
几乎从任何地方都能看到洞穴。
它们形成了很多重叠的表面（举个例子来说，一个多边形在另外一个多边形的前面）。
你看下这个场景，这对性能的透支简直是疯了！ 所有这些混乱的重叠多边形会在个人电脑上浪费大量的渲染时间，但是这个问题在那些使用的基于瓦片的延迟渲染（Tile-Based Deferred Rendering，TBDR）架构的移动设备上会更加严重，主要是由于这种渲染架构处理碎片的方式会导致在处理混乱重叠的多边形会有更多的性能消耗。
提示：TBDR全称Tile-based Deferred Rendering，它是Power VR独特的TBR技术的一种延伸实现手段。TBR/TBDR通过将每一帧画面划分成多个矩形区域，并对区域内的所有像素分别进行Z值检查，在任务进入渲染阶段之前就将被遮挡的不可见像素剔除掉。由于在渲染之前进行Z-culling操作，这种充满想象力的做法极大地，甚至可以说海量的削减了最终被渲染像素的数量，不仅大幅降低了系统对像素的处理压力，更极大的节约了显存带宽及空间的开销。尽管TBDR不再像传统的TBR那样需要通过CPU来进行Z值检查，但是TBDR过程需要对画面内所有的像素进行一次“额外”的load过程，这个过程本身无论从哪个角度来讲都是与节约 显存带宽 背道而驰的，尤其是在复杂度极高但Z-Occlusion（Z闭塞）并不严重的场景中更是如此。另外，尽管对画面的矩形划分越细密，GPU对像素进行Z判断的效率和准确率越高，但TBDR过程对画面的矩形切割非常机械，这种划分经常会导致很多多边形和纹理被Tiles所切割，这些多边形和纹理都必须经过2次甚至4次读取才能保持自身形态的“完整”，这无疑加重了几何和纹理处理过程的负担。如果场景的多边形数量较多，这种切割还会导致场景缓冲区被快速的消耗殆尽，场景缓冲区的溢出会直接导致Z判断延迟的急剧增大，这对整个处理过程的影响是巨大的。
通俗的说，TBDR需要在屏幕上画很多很多的小格子，然后把格子里的所有像素都拿出来做某种检查，没通过检查的“坏”像素就会被丢掉。尽管丢掉这些没通过检查的像素可以让后面的工作量减小，但这个检查本身对渲染没有任何意义，所以没有被丢掉的像素就相当于走了一遍无用的过场。与此同时，划分小格子的过程会切坏很多多边形和纹理，想要让这些多边形和纹理能够从“误伤”中幸存下来，你切了它们多少刀就要重新读取它们多少次。如果多边形本身就很多，被误伤的概率就更大，这会使得系统的某种缓存被快速消耗干净，缓存没了，系统干什么都不可能快得起来。
使用基于瓦片延迟渲染架构的GPU，比如苹果设备上的PowerVR可以非常有效的执行隐面消除（Hidden Surface Removal），但是在记录一组有序的屏幕像素的时候消耗却非常大。这种架构在屏幕上的内容非常简单的时候非常有效，但是场景的复杂度是与每个像素上着色片段的数量是成正比的。在《我的世界》里面的典型洞穴场景中，一个像素上的着色片段的数量是非常非常庞大的（最极端的情况下，一个像素上有几百个三角形要进行渲染），这会对性能有非常明显的影响。在有洞穴场景的基准测试中，即使是最新版本的iPad Mini Retina也没有办法以超过40fps的速度进行渲染，而另外一些较老的设备比如iPad Mini/iPad 2甚至维持一个可玩的帧率都非常的艰难。
为了让大部分的手机能够支持洞穴，我们绝对需要一种方法可以在不需要洞穴的时候将它们隐藏掉，这样就可以降低大部分的渲染消耗了。。。但是为了做到这一点，我们需要找到一种新的方法，因为我们已经探讨了很多方法，但是这些方法其实并没有真正做到这一点： 人们之前已经尝试过的办法
1，《我的世界》个人电脑版使用过OpenGL里面的先进方法
最初为了解决电脑上的性能消耗的问题，我们使用过当时还很先进的OpenGL函数，叫做硬件遮挡查询（Hardware Occlusion Query）:它会绘制一个大小为16x16x16的立方体，然后向GPU查询是否这个立方体的每个像素都能被看到。（通过硬件遮挡查询，我们能够直接获得所提交的物体是否被绘制到场景中。从而得知物体是否被遮挡，被遮挡的物体是不会出现在场景中的，如果直接提交整个物体mesh，遮挡查询的开销显然太大了。我们只要提交物体的轴向包围盒即可）。
如果查询的结果是立方体的每个像素都能被看到，那么整个物体都被认为是能被看到的，就需要把它给绘制出来。
这在某些GPU上是可以工作的（主要是桌面电脑上Nvidia系列的各种显卡），但不幸的是这种方法并不像听上去那样能在一半的情况下起作用：除了需要多渲染很多立方体这会导致渲染更慢以外，GPU里面的处理在本质上是异步的。
这也就是说，你的GPU在任何时候返回的结果都会比CPU正在做的事情要延迟1-3帧。
所以如果不做大量的细节工作，让渲染这些代替品以及读取渲染的结果能发生在同一帧的话会导致GPU停下来等待CPU。
如果不是Nvidia在驱动层做了很多优化，这个过程其实可能是非常慢的。
并且硬件遮挡查询这个功能仅在运行OpenGL ES 3.0上的设备可用，这已经是设备里面最快的那一批了(我们的任务是给比较慢的那批设备找到一个方法能够让洞穴渲染的更快)。
2，检查一侧能看到的材质是否都是不透明的
许多人（包括我）想到了一个可以运行在CPU上的算法，它会检查16x16x16块的某一面是否都由不透明的小块组成，如果都是不透明的那么其实就形成了一个我们可以做裁剪的墙。
如果一个物体完全是由这样的不透明面覆盖，那么隐藏这个物体将是安全的。
然而事实却有点让人失望。在实践中发现洞穴的分布非常的广阔而能找到的不透明的墙却非常的罕见，而且一个块的6个面都是不透明的概率非常低：100个块中只有1个可以通过这种方法进行剔除。 发散性的思考
其实之前的算法也没有那么糟糕，即使它们是不可行的-事实上，这些方法是我们最终在0.9版本的《我的世界》移动版和《我的世界》个人电脑版里面采用的做法的基础。
它只需要一个小的突破就可以变得可行。
这个想法其实挺简单的：如果我们不去判断那个隔离小块物体的墙，而是去检测那些通过不透明墙连接起来的小块呢？
毕竟我们知道我们会从哪个方向看向这些物体，这是一个我们可以使用的信息，可以通过对我们的联通图结构提交一些更加具体的请求。
从我所在的方向飞过来然后从A面那边飞进物体块，有可能从B面飞出物体块么？
回答这个问题是相当快的，并且对每个物体块只要求15个比特长度的存储信息，每两个面的组合对应一个比特-但是物体块的每个不透明面发生了变化都要把这15个比特位都更新一遍。
这实际是一个比较耗的操作（在大部分设备上我尝试的结果是0.1-0.2毫秒），如果这个操作是在主线程中完成的，情况将会更糟。事实上，无论是《我的世界》移动版还是《我的世界》个人电脑版（感谢Dinnerbone杰出的工作）现在都在辅助线程完成这个工作！
重建连通图
如果要在不透明块发生变化的时候对物体块建立连通图其实是相当简单直观的，它遵循如下一个简单的算法：
对于每个不透明的块。
使用一个空的面的集合开启3D填充。
每次填充试图退出物体块的边界的时候，会往面的集合里面添加这个面。
当填充完成的时候，把所有添加到面集合里面的面都连接起来。
这里有一个javascript做的样例，在里面尝试放置和移除不透明的块看下在2D情况下是如何工作的：
每种颜色代表一种不同的填充，深色块代表不通向任何地方。绿色的线说明了哪些面可以看到其他面。
在所有的物体块都通过它们的可见面连接在一起以后，是时候开始考虑如何使用这张连通图来决定我们要在屏幕上显示什么了，而这正是事情开始变得有趣的开始！
我会在第二部分里面尽力解释可见性图是如何使用的，希望讲的这些东西不要太无聊：）
近期热文：
经验分享丨项目实践项目孵化丨渠道发行做有梦想的游戏人
-GAME AND DREAM-